Link state routing protocols are a class of routing protocols that make visible, by broadcast, to every station/router in the network the set of links, and their states in the communication graph. The state could indicate a coarse ON-OFF representation or more detailed representation of the cost of link, which is used for computing optimal routes. Link state routing protocols have a significant importance in the history of routing in data networks. A notable one was in the stabilization of the ARPANET routing protocol.
Current day intra-domain routing protocols such as OSPF also employ link state mechanism. In OSPF, the cost (also called metric) of an interface link is an indication of the overhead required to send packets across a certain interface, i.e., the cost of an interface is inversely proportional to the bandwidth of that interface. In the past decade, link state mechanisms have also been adopted to Mobile Ad Hoc Networks (MANETs), e.g., OLSR protocol.
Most methods, to date, have been based on constructing a Connected Dominating Set (CDS) via local pruning. Local pruning, as used in relation to the prior art methods, refers to the mechanism by which a host which is aware of only local neighborhood information (typically k-hop neighborhood information), prunes edges or vertices for broadcast. In other words, it is the process by which a host selects only a subset of the link-state information, via pruning, that is broadcast in the routing domain. Connected Dominating Sets (CDS) are a subset of vertices/nodes, which are routers in this context, that are used to construct a flooding overlay network such that any information flooded via the CDS reaches all the nodes (routers) in the routing domain/autonomous system. However, such methods based on CDS guarantee only properties of nodes/vertices, and not that of paths. Consequently, CDS based methods cannot trivially guarantee that paths with QoS are preserved during the local pruning operation.